<?php

namespace App\Console\Commands;

class ZTestCommand extends BaseCommand
{
    /**
     * The name and signature of the console command.
     *
     * 现有整数 n 和 k （k <= n!），求 n 的 排列组合 的 第 k 个值。
     * 如 n = 3，其排列组合有：["123","132","213","231","312","321"] ;
     * 当 k = 4，其结果就是上面数组的第 4 个元素，即： "231"
     *
     * @example php /www/message/artisan ztest --n=3 --k=4
     *
     * @var string
     */
    protected $signature = 'ztest {--n=} {--k=}';

    /**
     * The console command description.
     *
     * @var string
     */
    protected $description = 'Create sub table for nice_msg_send_{Ymd} .';

    /**
     * Create a new command instance.
     *
     * @return void
     */
    public function __construct()
    {
        parent::__construct();
    }

    /**
     * Execute the console command.
     *
     * @return mixed
     */
    public function handler()
    {
        $n = $this->option('n');
        $k = $this->option('k');
        // 方法一： 最优解，直接算出k所在的值
        $ary = $this->getNAryBySort($n, $k);
        // 方法二： 先生成foreach代码z，再eval执行，最后根据k返回
        //$ary = $this->getNAryByCode($n);
        // 方法三： 坚持使用foreach生成排列组合数组，再根据k返回
        //$ary = $this->getNAryByForeach($n);$ary = explode(',', str_replace('-', '', $ary));
        return [
            //'res' => getVal($ary, $k - 1),
            'res' => $ary,
        ];
    }

    /**
     * get n array by sort
     * @param $n
     * @param $k
     * @return string
     */
    public function getNAryBySort($n, $k)
    {
        $ary = range(1, $n);
        // n=4 k=13 -> k = 4*3 + 3*0 + 2*0 + 1*1 -> [3, 0, 0, 1] -> 3124
        $sort = [];
        $tmp = $k;
        for ($i = $n; $i > 0; $i--) {
            $int = intval($tmp / $i);
            if ($i <= 1) {
                $sort[] = $tmp % $n;
            } else {
                $sort[] = $int;
                $tmp = $tmp - $int * $i;
            }
        }
        $str = [];
        $sortExt = $sort;
        rsort($sortExt);
        foreach ($sortExt as $key => $val) {
            if (!$val) {
                continue;
            }
            $keys = array_search($val, $sort);
            if (!$key) {
                $str[$keys] = $ary[$val -  1];
            } else {
                $str[$keys] = max($ary);
            }
            $ary = array_merge(array_diff($ary, [$str[$keys]]));
        }
        foreach ($sort as $key => $val) {
            if (!$val) {
                $str[$key] = $ary[0];
                $ary = array_merge(array_diff($ary, [$ary[0]]));
            }
        }
        ksort($str);
        return implode('', $str);
    }

    /**
     * get permutation and combination from integer n
     *
     * ****************************************************
     * // n = 3
     * $result = [];
     * foreach ($ary as $key => $val) {
     *     $s0 = $val;
     *     foreach ($ary as $k => $v) {
     *         $s1 = $s0 . "-" . $v;
     *         $vList = explode("-", $s0);
     *         if (in_array($v, $vList)) {
     *             continue;
     *         }
     *         foreach ($ary as $p => $q) {
     *             $s2 = $s1 . "-" . $q;
     *             $vList = explode("-", $s1);
     *             if (in_array($q, $vList)) {
     *                 continue;
     *             }
     *             $result[] = str_replace("-", "", $s2);
     *         }
     *     }
     * }
     * return $result;
     * ****************************************************
     *
     * @param integer $n
     * @return mixed
     */
    public function getNAryByCode($n)
    {
        $ary = range(1, $n);
        $code = '$result = [];
        foreach ($ary as $key => $val) {
        $s0 = $val;' . PHP_EOL;
        $endLess = PHP_EOL . '}' . PHP_EOL;
        for ($i = 1; $i < count($ary); $i++) {
            $code .= 'foreach ($ary as $k'.$i.' => $v'.$i.') {
            $s'.$i.' = $s'.($i - 1).' . "-" . $v'.$i.';
            $vList = explode("-", $s'.($i - 1).');
            if (in_array($v'.$i.', $vList)) {
                continue;
            }' . PHP_EOL;
            if ($i >= count($ary) - 1) {
                $code .= '$result[] = str_replace("-", "", $s'.$i.');' . PHP_EOL;
            }
            $endLess .= '}' . PHP_EOL;
        }
        $code .= $endLess . 'return $result;' . PHP_EOL;
        return eval($code);
    }

    /**
     * @param $n
     * @param array $ary
     * @param string $res
     * @param string $result
     * @return string
     */
    public function getNAryByForeach($n, $ary = [], $res = '', $result = '') {
        static $i = 0;
        $size = $this->getNSize($n);
        $ary = $ary ?: range(1, $n);
        $res = $res ?: $ary[0];
        foreach ($ary as $key => $val) {
            $vList = explode('-', $res);
            var_dump(json_encode($ary) . "---{$val}---" . '------:' . $res);
            if ($i >= $size) {
                return $result;
            }
            if (count($vList) >= $n) {
                $i++;
                $nAry = range(1, $n);
                $result .= ($result ? ',' : '') . $res;
                // next
                $next = '';
                // 2-3-1 -> 3-1
                foreach ($vList as $k => $v) {
                    if (!$k) {
                        $min = min(array_diff($vList, [$v]));
                        if (end($vList) != $min) {
                            $next .= $v;
                            continue;
                        } else {
                            // end
                            if ($v >= $n) {
                                return $result;
                            } else {
                                $next = $v + 1;
                                $vList = $nAry;
                            }
                            break;
                        }
                    }
                    if ($v < $n) {
                        // 1-2-3- -> 1-3-2
                        $next .= ($next ? '-' : '') . $vList[$k + 1];
                        break;
                    } else {
                        $next .= ($next ? '-' : '') . $v;
                        continue;
                    }
                }
                if (empty($next)) {
                    return $result;
                }
                return $this->getNAryByForeach($n, $vList, $next, $result);
            }
            if (count($vList) !== count(array_unique($vList))) {
                continue;
            }
            if (count($vList) === 1) {
                $val = $vList[0];
            }
            // 2-3 -> 3-1
            $nAry = array_merge(array_diff($ary, [$val]));
            return $this->getNAryByForeach($n, $nAry, $res . '-' . $nAry[0], $result);
        }
        return $result;
    }

    /**
     * get n size
     * @param $n
     * @param int $res
     * @return int
     */
    public function getNSize($n, $res = 0)
    {
        $res = $res ?: $n;
        if ($n <= 1) {
            return $res;
        }
        $n--;
        return $this->getNSize($n, $res * $n);
    }

}
